package DataStructureAndAlgorithm.Acwing.DP.背包问题DP.零一背包DP.至少背包求解;
/*
dp[i][j][k]：所有从前i个中选，并且氧气总量不少于j，氮气总量不少于k的选法
*/

//未优化代码
 import java.util.Scanner;

 class Main{
     public static void main(String[] args){
         Scanner in = new Scanner(System.in);
         int m = in.nextInt();
         int n = in.nextInt();
         int k = in.nextInt();
         int[] a = new int[k + 1];
         int[] b = new int[k + 1];
         int[] c = new int[k + 1];
         for (int i = 1; i <= k; i++){
             a[i] = in.nextInt();
             b[i] = in.nextInt();
             c[i] = in.nextInt();
         }
         int[][][] dp = new int[k + 1][m + 1][n + 1];
         for (int i = 0; i <= k; i++){
             for (int j = 0; j <= m; j++){
                 for (int t = 0; t <= n; t++){
                     //初始化所有不合法状态为无穷大
                     //注意：设置为Integer.MAX_VALUE会因为后面还有相加操作而导致溢出
                     dp[i][j][t] = 99999999;
                 }
             }
             //初始化所有不选的情况重量为0；
             dp[i][0][0] = 0;
         }
         for (int i = 1; i <= k; i++){
             for (int j = 0; j <=m; j++){
                 for (int t = 0; t <= n; t++){
                     //根据状态定义，当j - a[i] < 0 或者 t - b[i] < 0表示当前方案对于任意选法都成立，
                     //此时体积对应的最小值是任何一个气缸都不选的情况，即重量为0
                     //也即对于的是dp[i - 1][0][0]的情况
                     dp[i][j][t] = Math.min(dp[i - 1][j][t],dp[i - 1][Math.max(0,j - a[i])][Math.max(0,t - b[i])] + c[i]);
                 }
             }
         }
         System.out.print(dp[k][m][n]);
     }
 }


//优化后代码
//import java.util.Scanner;
//        import java.util.Arrays;
//class Main{
//    public static void main(String[] args){
//        Scanner in = new Scanner(System.in);
//        int m = in.nextInt();
//        int n = in.nextInt();
//        int k = in.nextInt();
//        int[][] dp = new int[m + 1][ n + 1];
//        for (int i = 0; i <= m; i++){
//            Arrays.fill(dp[i],9999999);
//        }
//        dp[0][0] = 0;
//        int a,b,c;
//        for (int i = 0; i < k; i++){
//            a = in.nextInt();
//            b = in.nextInt();
//            c = in.nextInt();
//            for (int j = m; j >= 0; j--){
//                for (int t = n; t >= 0; t--){
//                    dp[j][t] = Math.min(dp[j][t],dp[Math.max(0,j - a)][Math.max(0,t - b)] + c);
//                }
//            }
//        }
//        System.out.print(dp[m][n]);
//    }
//}

/*
潜水员为了潜水要使用特殊的装备。

他有一个带2种气体的气缸：一个为氧气，一个为氮气。

让潜水员下潜的深度需要各种数量的氧和氮。

潜水员有一定数量的气缸。

每个气缸都有重量和气体容量。

潜水员为了完成他的工作需要特定数量的氧和氮。

他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
输入格式

第一行有2个整数 m，n

。它们表示氧，氮各自需要的量。

第二行为整数 k

表示气缸的个数。

此后的 k
行，每行包括ai，bi，ci，3个整数。这些各自是：第 i

个气缸里的氧和氮的容量及气缸重量。
输出格式

仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。
数据范围

1≤m≤21
,
1≤n≤79,
1≤k≤1000,
1≤ai≤21,
1≤bi≤79,
1≤ci≤800

输入样例：

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

输出样例：

249

 */
